import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Text4 {
    //15.三数字之和
//    public List<List<Integer>> threeSum(int[] nums) {
//        Arrays.sort(nums);
//        List<List<Integer>> ret = new ArrayList<>();
//
//        int n = nums.length;
//        for (int i = 0 ; nums[i] < 0; i++){
//
//            int left = i + 1 , right = n - 1;
//            int tmp = -nums[i];
//            while(left < right){
//                if (nums[left]+nums[right]<tmp){
//                    left++;
//                } else if (nums[left]+nums[right]>tmp){
//                    right--;
//                } else {
//                   ret.add(new ArrayList<Integer>(Arrays.asList(nums[left],nums[right],nums[i])));
//                }
//            }
//
//        }
//        return ret;
//    }

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();

        int n = nums.length;
        for (int i = 0 ; i<n; ){
            if(nums[i]>0) break;
            int left = i + 1 , right = n - 1;
            int tmp = -nums[i];
            while(left < right){
                if (nums[left]+nums[right]<tmp){
                    left++;
                } else if (nums[left]+nums[right]>tmp){
                    right--;
                } else {
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[left],nums[right],nums[i])));
                    left++;
                    right--;
                    //错误点：去重操作
                    while(nums[left] == nums[left-1] && left<right){
                        left++;
                    }
                    while(nums[right] == nums[right+1] && left<right){
                        right--;
                    }
                }
            }
            i++;
            while( i<n && nums[i] == nums[i - 1]){
                i++;
            }

        }
        return ret;
    }

}
